# 作者: 赵若云
# 2025年02月22日09时58分27秒
# 3478783573@qq.com


class Node(object):
    """
    节点类
    """

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """树类"""

    def __init__(self):
        self.root = None  # 树根
        self.myQueue = []  # 辅助队列

    def add_node(self, elem):
        """为树添加节点"""
        new_node = Node(elem)
        self.myQueue.append(new_node)
        if self.root is None:  # 若树根为空
            self.root = new_node  # 新结点作为树根
        else:
            if self.myQueue[0].lchild is None:
                self.myQueue[0].lchild = new_node
            else:
                self.myQueue[0].rchild = new_node
                self.myQueue.pop(0)  # 出队

    def pre_order(self, current_node: Node):
        """前序遍历"""
        if current_node:
            print(current_node.elem, end=" ")
            self.pre_order(current_node.lchild)  # 遍历左子树
            self.pre_order(current_node.rchild)  # 遍历右子树

    def mid_order(self, current_node: Node):
        """中序遍历"""
        if current_node:
            self.mid_order(current_node.lchild)  # 遍历左子树
            print(current_node.elem, end=" ")
            self.mid_order(current_node.rchild)  # 遍历右子树

    def last_order(self, current_node: Node):
        """后序遍历"""
        if current_node:
            self.last_order(current_node.lchild)  # 遍历左子树
            self.last_order(current_node.rchild)  # 遍历右子树
            print(current_node.elem, end=" ")

    def level_order(self):
        """层序遍历"""
        queue = []
        queue.append(self.root)
        while queue:
            current_node = queue.pop(0)
            print(current_node.elem, end=" ")
            if current_node.lchild:
                queue.append(current_node.lchild)
            if current_node.rchild:
                queue.append(current_node.rchild)


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        tree.add_node(i)

    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)
    print()
    tree.level_order()
